package map;
import java.util.*;
public class MapSetProblem {
    /*
    * 136. 只出现一次的数字
    * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
    */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //遍历统计每个数字出现的次数
        for(int num : nums){
            int count = map.getOrDefault(num, 0);
            map.put(num, count + 1);
        }

        int ret = 0;
        //找出只出现一次的数字
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue() == 1){
                ret =  entry.getKey();
                break;
            }
        }

        return ret;
    }

    /*
    * 771. 宝石与石头
    * 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
    * stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    * 字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
    * */
    public int numJewelsInStones(String jewels, String stones) {
        // int cnt = 0;
        // for(int i = 0; i < stones.length(); i++){
        //     if(jewels.indexOf(stones.charAt(i)) != -1){
        //         cnt++;
        //     }
        // }
        // return cnt;

        //创建set，储存宝石
        Set<Character> set = new HashSet<>();
        //将代表宝石的字符串转化为字符数组进行遍历，添加到set中
        for(char c : jewels.toCharArray()){
            set.add(c);
        }

        int cnt = 0;
        //统计石头中种含宝石的数量
        for(char c : stones.toCharArray()){
            if(set.contains(c)){
                cnt++;
            }
        }
        //返回宝石的数量
        return cnt;
    }

    /*
    * 旧键盘
    * 旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该
    * 输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
    * */
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNext()) { // 注意 while 处理多个 case
                //输入两个字符串
                String s1 = in.next();
                String s2 = in.next();
                //创建一个HashSet,用于储存字符串2的字符
                Set<Character> set1 = new HashSet<>();
                //将字符串中的小写字母转化为大写字母
                s1 = s1.toUpperCase();
                s2 = s2.toUpperCase();
                //将s2的字符储存到set1中
                for(char c : s2.toCharArray()){
                    set1.add(c);
                }
                //用储存字符串s2中没有的字符
                Set<Character> set = new HashSet<>();
                //String s = "";
                //遍历字符串s1
                for(char c : s1.toCharArray()){
                    //set2没有的字符，且set中没有的字符则输出打印
                    if(!set1.contains(c) && ! set.contains(c)){
                        System.out.print(c);
                        set.add(c);
                    }
                }
                System.out.println();
            }
        }
    }
    /*
    * 138. 随机链表的复制
    * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
    * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
    * 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针
    * 能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
    * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，
    * 同样有 x.random --> y 。返回复制链表的头节点。
    * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
    * val：一个表示 Node.val 的整数。
    * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
    * 你的代码 只 接受原链表的头节点 head 作为传入参数。
    * */

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        //创建map，key储存老节点，value储存新结点
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        //遍历链表，创建新节点
        while(cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        //遍历链表，按链表调整新结点的next、random的指向
        while(cur != null){
            //获取新节点
            Node newNode = map.get(cur);
            //获取新节点的下一个结点
            Node newNodeNext = map.get(cur.next);
            //新结点的next指向下一个新结点
            newNode.next = newNodeNext;
            if(cur.random == null){
                newNode.random = null;
            }else{
                newNode.random = map.get(cur.random);
            }

            cur = cur.next;
        }
        //获取新链表的头结点
        Node newHead = map.get(head);
        return newHead;
    }

    /*
    * 217. 存在重复元素
    * 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
    * */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            //检查是否添加成功，失败说明有两个相同的数，返回true
            if(!set.add(num)){
                return true;
            }
        }


        // Map<Integer, Integer> map = new HashMap<>();
        // for(int num : nums){
        //     int cnt = map.getOrDefault(num, 0);
        //     if(cnt == 1){
        //         return true;
        //     }
        //     map.put(num, cnt + 1);
        // }

        // for(Map.Entry<Integer, Integer> entrySet : map.entrySet()){
        //     if(entrySet.getValue() >= 2){
        //         return true;
        //     }
        // }

        //没有相同的两个数，返回false
        return false;
    }

    /*
    * 219. 存在重复元素 II
    * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
    * 满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
    * */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //创建map，key储存nums[index], value储存下标index
        Map<Integer, Integer> map = new HashMap<>();
        for(int index = 0; index < nums.length; index++){
            //如果插入的 key 对应的 value 已经存在，则执行 value 替换操作，
            //返回旧的 value 值，如果不存在则执行插入，返回 null

            //获得上次添加key的下标
            Integer oldIndex = map.put(nums[index], index);
            if(oldIndex != null && (index - oldIndex) <= k){
                //上次下标不为空，且本次下标减去上次下标小于等于k，返回true
                return true;
            }
        }
        //不存在下标之差的绝对值小于等于 k 且相等的两个数，返回false
        return false;
    }

    public static void main(String[] args) {
        System.out.println();
    }
}
